//********************************************************************************
//
// File :           ph02_enum_sort_cluster.cpp
//
// Description :    enum_sort arrays using cluster
//
// Dependencies:    mpi.h
//
// Author :         UlMonkey1987( WU Kan )
//
// Stu NO. :        2010212404
//
// Date :           2011-4-17
//
//********************************************************************************

#include "mpi.h"

#include <iostream>
#include <fstream>
#include <iomanip>

#include <cstdlib>
#include <cmath>

#include <string>

using namespace std;

// bool readData( const string& strTestDataPath, long* pNum, unsigned long numN )
bool readData( const string& strTestDataPath, long* pNum, unsigned long numN )
{
    if ( 0 == pNum ) return false;

    ifstream fin( strTestDataPath.c_str(), iostream::binary );

    char* pByteData = ( char* ) pNum;

    fin.read( pByteData, numN * sizeof( long ) );

    return true;
}
//

// unsigned long calc_rank( const long* pNum, const unsigned long numN, const unsigned long curIndex )
unsigned long calc_rank( const long* pNum, const unsigned long numN, const unsigned long curIndex )
{
    unsigned long ret_rank = 0;

    for ( unsigned long i = 0; i < numN; i ++ )
    {
        if ( ( pNum[i] < pNum[curIndex] ) || ( i < curIndex && pNum[i] == pNum[curIndex] ) )
            ret_rank ++;
    }

    return ret_rank;
}
//

int main( int argc, char* argv[] )
{
    if ( argc < 4 )
    {
        cout << "error : lack args." << endl;
        cout << "usage : " << "<program_name>" << " <test_data_path> <n> <output_file_path>." << endl;
        return 1;
    }

    string strTestDataPath = string( argv[1] );     // data src path
    unsigned long numN = atoi( argv[2] );      // numN
    string strOutPath = string( argv[3] );      // output path

//     // for test
//     string strTestDataPath = "2.raw";
//     unsigned long numN = 100;
//     string strOutPath = "result.txt";
//     // ! for test

    const int MAX_PROC_NAME_LEN = 256;      // max length of a processor name

    int procN;                           // number of process
    int curProcId;                          // id of current process
    char curProcName[MAX_PROC_NAME_LEN];      // name of current process
    int curProcNameLen;                     // the length of current process name

    MPI_Init( &argc, &argv );
    MPI_Comm_size( MPI_COMM_WORLD, &procN );
    MPI_Comm_rank( MPI_COMM_WORLD, &curProcId );
    MPI_Get_processor_name( curProcName, &curProcNameLen );

    cout << "Process " << curProcId << " Running..." << endl << endl;

    double timeStart, timeEnd, timeCost;        // start time, end time, duration time

    long* pNum = new long[numN];                // data to be sorted
    int* pNumN = new int[procN];                    // data count for each process
    int* pOffset = new int[procN];                  // offset for each process
    long* pMergedRank = 0;                      // final rank for every elem
    long* pNumRankTemp = 0;                         // temp rank for every elem

    if ( 0 == curProcId )
    {
        // read data
        readData( strTestDataPath, pNum, numN );
//         for ( unsigned long i = 0; i < numN; i ++ )
//             pNum[i] = numN - i;
        // ! read data

        // timer started
        timeStart = MPI_Wtime();
        // ! timer started

        // calculate data-counts and offset-counts for every elem
        unsigned long numNPerProcBase = numN / procN;
        unsigned long numNRemain = numN % procN;

        for ( long i = 0; i < procN; i ++ )
        {
            pNumN[i] = numNPerProcBase;
            if ( numNRemain > 0 ) { pNumN[i] ++; numNRemain --; }
        }

        pOffset[0] = 0;
        for ( long i = 1; i < procN; i ++ )
            pOffset[i] = pOffset[i-1] + pNumN[i-1];
        // ! calculate data-counts and offset-counts for every elem

        pMergedRank = new long[numN];
    }

    MPI_Bcast( pNum, numN, MPI_LONG, 0, MPI_COMM_WORLD );           // total data to be sorted
    MPI_Bcast( pNumN, procN, MPI_INT, 0, MPI_COMM_WORLD );              // data count for each process
    MPI_Bcast( pOffset, procN, MPI_INT, 0, MPI_COMM_WORLD );        // data offset for each process

    unsigned long curNumN = pNumN[curProcId];                   // data count of current process
    unsigned long curOffset = pOffset[curProcId];                   // data offset of current process

    pNumRankTemp = new long[curNumN];                               // temp rank
    for ( unsigned long i = 0; i < curNumN; i ++ )
    {
        unsigned long curIndex = i + curOffset;                     // current data element index

        unsigned long rankIndex = calc_rank( pNum, numN, curIndex );        // rank current data element

        pNumRankTemp[i] = rankIndex;                                            // set current data element rank
    }

    MPI_Gatherv( pNumRankTemp, curNumN, MPI_LONG, pMergedRank, pNumN, pOffset, MPI_LONG, 0, MPI_COMM_WORLD );       // gather all data ranks

    delete []pOffset; pOffset = 0;
    delete []pNumN; pNumN = 0;
    delete []pNumRankTemp; pNumRankTemp = 0;

    if ( 0 == curProcId )
    {
        // rearrange data according to the ranks
        long* pNumTemp = new long[numN];
        for ( unsigned long i = 0; i < numN; i ++ )
            pNumTemp[i] = pNum[i];

        for ( unsigned long i = 0; i < numN; i ++ )
        {
            unsigned long dstIndex = pMergedRank[i];
            pNum[dstIndex] = pNumTemp[i];
        }
        delete []pNumTemp; pNumTemp = 0;
        // ! // rearrange data according to the ranks

        // timer stopped
        timeEnd = MPI_Wtime();
        // ! timer stopped

//         for ( unsigned long i = 0; i < numN; i ++ )
//         {
//             cout << pNum[i];
//             if ( numN - 1 != i ) cout << ",";
//         }
//         cout << endl;

        timeCost = timeEnd - timeStart;
        //cout << endl << "cost time : " << timeCost << endl;

        delete []pNum; pNum = 0;
        delete []pMergedRank; pMergedRank = 0;

        // output result
        ofstream fout( strOutPath.c_str(), ios::app );
        fout << "cluster\t" << strTestDataPath << "\t" << "enum_sorting\t" << procN << "\t" << numN << "\t" << setprecision( 2 ) << timeCost << "\n";
        // ! output result

        cout << endl << "cluster " << strTestDataPath << " " << "enum_sorting " << procN << " " << numN << " " << setprecision( 2 ) << timeCost << endl;
    }

    // system( "pause" );

    MPI_Finalize();

    return 0;
}
